package dp;

public class _22_121_买卖股票的最佳时机 {
    public int maxProfit(int[] prices) {

    	int dp[][] = new int[prices.length][2];
    	// 第一天持有，则减去金额
    	dp[0][0] -= prices[0];
    	// 第一天不持有，则是0
    	dp[0][1] = 0;
    	for(int i = 1; i < prices.length; i++) {
    		// 持有 则取前一天持有的值与今天持有的值 取最大值 (今天买入则减去对应金额
    		// 由于持有值都是负数，所以取到的最大值就是买入的最少金额
    		dp[i][0] = Math.max(dp[i-1][0], -prices[i]);
    		// 不持有 则取前一天不持有的值与前一天持有减去今天不持有的值 取最大值
    		// dp[i-1][0] + prices[i]为前一天持有加上今天售出的利润
    		// 该值与前一天出售的利润进行比较取最大值，就能一直保持最大值
    		dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i]);
    	}
    
    	return dp[prices.length-1][1];
    }
    
    public static void main(String[] args) {
    	int prices[] = {7,6,4,3,1};
		System.out.println(new _22_121_买卖股票的最佳时机().maxProfit(prices));
	}
}
